// 图像渲染
class Solution
{
private:
    vector<vector<int>> distance = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        // 0、检查填充颜色是否和原来颜色一样
        int curColor = image[sr][sc];
        if(curColor == color) return image;
        // 1、数据初始化
        int m = image.size();
        int n = image[0].size();
        queue<pair<int, int>> q;
        q.push(make_pair(sr, sc));
        image[sr][sc] = color;
        // 2、bfs
        while(!q.empty())
        {
            // 拿出队头元素
            int i = q.front().first;
            int j = q.front().second;
            q.pop();
            // 检查上下左右四个元素
            for(int d = 0; d < 4; ++d)
            {
                int ni = i + distance[d][0];
                int nj = j + distance[d][1];
                if(ni < 0 || ni >= m || nj < 0 || nj >= n || image[ni][nj] != curColor)
                {
                    continue;
                }
                image[ni][nj] = color;
                q.push(make_pair(ni, nj));
            }
        }
        // 3、返回值
        return image;
    }
};

// 01矩阵
class Solution
{
private:
    vector<vector<int>> distance =
            {
                    {0, 1},
                    {0, -1},
                    {1, 0},
                    {-1, 0}
            };
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
    {
        // 1、数据初始化
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> super(m, vector<int>(n));
        auto ret = super;
        queue<pair<int, int>> q;

        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(mat[i][j] == 0)
                {
                    super[i][j] = 1;
                    q.push(make_pair(i, j));
                }

        // 2、bfs
        while(!q.empty())
        {
            // 取出队头数据
            pair<int, int> front = q.front();
            int i = front.first;
            int j = front.second;
            q.pop();
            // 更新上下左右的数据
            for(int d = 0; d < 4; ++d)
            {
                int ni = i + distance[d][0];
                int nj = j + distance[d][1];
                if(ni < 0 || ni >= m || nj < 0 || nj >= n || super[ni][nj] == 1)
                {
                    continue;
                }
                ret[ni][nj] = ret[i][j] + 1;
                super[ni][nj] = 1;
                q.push(make_pair(ni, nj));
                // if(ni>=0 && ni<m && nj>=0 && nj<n && !super[ni][nj])
                // {
                //     q.push(make_pair(ni, nj));
                //     ret[ni][nj] = ret[i][j] + 1;
                //     super[ni][nj] = 1;
                // }
            }
        }
        // 3、返回值
        return ret;
    }
};

// 岛屿数量
class Solution
{
private:
    vector<vector<int>> distance =
            {
                    {0, 1},
                    {0, -1},
                    {1, 0},
                    {-1, 0}
            };

public:
    int numIslands(vector<vector<char>>& grid)
    {
        // 1、数据初始化
        int m = grid.size();
        int n = grid[0].size();
        queue<pair<int, int>> q;
        // 2、bfs
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == '1')
                {
                    ++ret;
                    q.push(make_pair(i, j));
                    while(!q.empty())
                    {
                        // 处理队头岛屿
                        auto front = q.front();
                        int row = front.first;
                        int col = front.second;
                        grid[row][col] = '0';
                        q.pop();
                        // 处理上下左右岛屿
                        for(int d = 0; d < 4; ++d)
                        {
                            int newRow = row + distance[d][0];
                            int newCol = col + distance[d][1];
                            if(newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || grid[newRow][newCol] != '1')
                            {
                                continue;
                            }
                            grid[newRow][newCol] = '0';
                            q.push(make_pair(newRow, newCol));
                        }
                    }
                }
            }
        }
        return ret;
    }
};

// 钥匙和房间
class Solution
{
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms)
    {
        // 1、数据初始化
        vector<bool> house(rooms.size());
        queue<int> q;
        q.push(0);
        // 2、bfs
        while(!q.empty())
        {
            int front = q.front();
            q.pop();
            if(house[front] == false)
            {
                house[front] = true;
                for(const auto e : rooms[front])
                {
                    q.push(e);
                }
            }
        }
        // 3、返回值
        return find(house.begin(), house.end(), false) == house.end();
    }
};

// 机器人移动范围
